import java.util.*;

public class T653 {
    //两数之和 二叉搜索树
    static boolean falg = false;
    static Set set = new HashSet();
    public static void main(String[] args) {
        int arr[] = {0, -1, 2, -3, 4};
        int k = -4;
        TreeNode root = addTree(arr);
        //getSort(root);
        System.out.println();
        boolean find = findTarget(root, 9);
        System.out.println(find);
    }
// O(n^2)
   /* public static boolean findTarget(TreeNode root, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list = preorder(root, list);
        System.out.println(list);//前序遍历结果
        for(int i =0;i<list.size();i++){
            int a = list.get(i);
            for(int j = 0;j<list.size();j++){
                if(j!=i&&a+list.get(j)==k){
                    return true;
                }
            }
        }
        return false;
    }*/
   /*public static ArrayList<Integer> preorder(TreeNode root, ArrayList<Integer> list) {
        if (root != null) {
            list.add(root.val);
            preorder(root.left, list);
            preorder(root.right, list);
        }
        return list;
    }*/
//On
public static boolean findTarget(TreeNode root, int k) {
    if(root == null){
        return false;
    }
    if(set.contains(k-root.val)){
        return true;
    }
    set.add(root.val);
    return findTarget(root.left,k) || findTarget(root.right,k);
}


    public static TreeNode addTree(int arr[]) {//层次遍历结果构建二叉树
        TreeNode root = new TreeNode();
        root.val = arr[0];
        TreeNode tmp = root;
        Queue queue = new LinkedList();
        int i = 0;
        while (root != null) {
            if (2 * i + 1 < arr.length) {
                root.left = new TreeNode(arr[2 * i + 1]);
                queue.add(root.left);
            }
            if (2 * i + 2 < arr.length) {
                root.right = new TreeNode(arr[2 * i + 2]);
                queue.add(root.right);
            }
            root = (TreeNode) queue.poll();
            i++;
        }
        return tmp;
    }

    public static void getSort(TreeNode p) {//层次遍历结果
        Queue queue = new LinkedList();
        while (p != null) {
            System.out.print(p.getVal() + " ");
            if (p.left != null) {
                queue.add(p.left);
            }
            if (p.right != null) {
                queue.add(p.right);
            }
            p = (TreeNode) queue.poll();
        }
    }
}


